package graphic;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。
 *
 * 示例 1:
 *
 * 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
 *
 *      0          3
 *      |          |
 *      1 --- 2    4
 *
 * 输出: 2
 * 示例 2:
 *
 * 输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
 *
 *      0           4
 *      |           |
 *      1 --- 2 --- 3
 *
 * 输出:  1
 * 注意:
 * 你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0]  相同，所以它们不会同时在 edges 中出现。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class CountComponents {

    private int[] table;
    public int countComponents(int n, int[][] edges) {
        if(n == 0 || edges == null || edges.length == 0 || edges[0].length == 0){
            return 0;
        }
        table = new int[n];
        for(int i = 0; i < n; i ++){
            table[i] = i;
        }
        for(int i = 0; i < edges.length; i ++){
            join(edges[i][0], edges[i][1]);
        }
        int count = 0;
        for(int i = 0; i < n; i++){
            if(table[i] == i){
                count ++;
            }
        }
        return count;
    }

    private int findRoot(int a){
        int root = a;
        while(table[root] != root){
            root = table[root];
        }
        table[a] = root;
        return root;
    }

    private void join(int a, int b){
        int rootA = findRoot(a);
        int rootB = findRoot(b);
        table[rootB] = rootA;
        if(b != rootB) {
            table[b] = rootB;
        }
    }

    public static void main(String[] args){
        System.out.println((new CountComponents()).countComponents(5, new int[][]{{0, 1}, {1, 2}, {3, 4}}));
    }
}
